//1.定义辅助类
class Node {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
}
class BinaerSearchTree {
    constructor() {
        this.root = null;
    }

    insert(key) {
        //1.创建节点
        const node = new Node(key);
        //2.执行插入
        //分情况讨论
        //1.树为空
        if (this.root === null) {
            this.root = node;
        } else {
            this.insertNode(this.root, node);
        }
    }
    insertNode(currentNode, node) {
        if (node.key > currentNode.key) {
            if (currentNode.right == null) {
                currentNode.right = node;
            } else {
                this.insertNode(currentNode.right, node);
            }
        } else {
            if (currentNode.left == null) {
                currentNode.left = node;
            } else {
                this.insertNode(currentNode.left, node);
            }
        }
    }
    inOrderTraverse() {
            this.inOrderTraverseNode(this.root);
        }
        //实现
    inOrderTraverseNode(node) {
        //基线条件
        if (node == null) {
            return
        }
        this.inOrderTraverseNode(node.left);
        console.log(node.key);
        this.inOrderTraverseNode(node.right)
    }

    preOrderTraverse() {
        this.preOrderTraverseNode(this.root);
    }
    preOrderTraverseNode(node) {
        if (node == null) {
            return;
        }
        console.log(node.key);
        this.preOrderTraverseNode(node.left)
        this.preOrderTraverseNode(node.right)

    }
    min() {
        return this.minNode(this.root);
    }
    minNode(node) {
        let current = node;
        while (current != null & current.left != null) {
            current = current.left;
        }
        return current.key;
    }
    max() {
        return this.maxNode(this.root);
    }
    maxNode(node) {
        let current = node;
        while (current != null & current.right != null) {
            current = current.right;
        }
        return current.key;
    }
    search(key) {
        let current = this.root;
        while (current != null) {
            if (key > current.key) {
                current = current.right;
            } else if (key < current.key) {
                current = current.left
            } else {
                return true;
            }
        }
        return false;
    }
    search2(key) {
        return this.searchNode(this.root, key);
    };
    //传入两个值：node,key
    searchNode(node, key) {
        if (node == null) {
            return false;
        }
        if (key > node.key) {
            return this.searchNode(node.right, key);
        } else if (key < node.key) {
            return this.searchNode(node.left, key);
        } else {
            return true;
        }
    }
}
const tree = new BinaerSearchTree();
tree.insert(11);
tree.insert(7)
tree.insert(3)
tree.insert(2)
tree.insert(431)
tree.insert(41)
tree.insert(231)
tree.insert(12)
tree.insert(37)
tree.insert(71)
tree.insert(27)
    // tree.inOrderTraverse();
    // console.log('object');
    // tree.preOrderTraverse();
    // console.log('object');
    // tree.postOrderTraverse();
console.log(tree.min());
console.log(tree.max());
let num = 5;
console.log('查找' + num, tree.search(num));